class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def createTree(self, nums: list):
        def level(index):
            if index >= len(nums) or nums[index] is None:
                return None
            root = TreeNode(nums[index])
            root.left = level(2 * index + 1)
            root.right = level(2 * index + 2)
            return root
        return level(0)

    def preorderOut(self, root: TreeNode) -> list:
        def preorder(root):
            if root:
                res.append(root.val)
                preorder(root.left)
                preorder(root.right)
        res = []
        preorder(root)
        return res

    def inorderOut(self, root: TreeNode) -> list:
        def preorder(root):
            if root:
                preorder(root.left)
                res.append(root.val)
                preorder(root.right)
        res = []
        preorder(root)
        return res

    def postorderOut(self, root: TreeNode) -> list:
        def postorder(root):
            if root:
                postorder(root.left)
                postorder(root.right)
                res.append(root.val)
        res = []
        postorder(root)
        return res

    def verifyPostorder(self, postorder: list) -> list:
        def verify(p1, p2):
            if p1 > p2:
                return True
            pos = p1
            while pos < p2 and postorder[pos] < postorder[p2]:
                pos += 1
            p = pos
            while pos < p2:
                if postorder[pos] < postorder[p2]:
                    return False
                pos += 1
            return verify(p1, p - 1) and verify(p, p2 - 1)
        if not postorder:
            return True
        return verify(0, len(postorder) - 1)

# 二叉搜索树的后序遍历序列
# 输入一个整数数组，判断是否为某二叉树的后序遍历结果。
# 参考：
#           5
#          / \
#         2   6
#        / \
#       1   3


s = Solution()
tree = [5, 2, 6, 1, 3]
# preorder = s.preorderOut(s.createTree(tree))
postorder = s.postorderOut(s.createTree(tree))
print('后序：', postorder)
res = s.verifyPostorder(postorder)
print(res)